package cn.edu.xjtu.carlWay.backTrack.reconstructItinerary;

import java.util.ArrayList;
import java.util.List;

/**
 * 332. 重新安排行程
 * 给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
 * <p>
 * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
 * <p>
 * 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
 * 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
 * <p>
 * https://leetcode-cn.com/problems/reconstruct-itinerary/
 */
public class Solution {
    public static void main(String[] args) {
        String[][] tick = {{"JFK", "SFO"}, {"JFK", "ATL"}, {"SFO", "ATL"}, {"ATL", "JFK"}, {"ATL", "SFO"}};
        List<List<String>> tickets = new ArrayList<>();
        for (String[] strs : tick) {
            tickets.add(new ArrayList<>(List.of(strs)));
        }
        Solution solution = new Solution();
        System.out.println("SFO".compareTo("JFK"));
        System.out.println(solution.findItinerary(tickets));
    }

    List<String> result = new ArrayList<>();
    ArrayList<String> path = new ArrayList<>();
    boolean[] used;

    /**
     * 使用bound和constrain剪枝，constrain还不会
     *
     * @param tickets
     * @return
     */
    public List<String> findItinerary(List<List<String>> tickets) {
        used = new boolean[tickets.size()];
        path.add("JFK");
        backtrack(tickets);
        return result;
    }

    private void backtrack(List<List<String>> tickets) {
        if (tickets.size() == path.size() - 1) {
            restore();
        } else {
            for (int i = 0; i < tickets.size(); i++) {
//                if (bound(i, tickets) && constrain(i, tickets)) {
                if (bound(i, tickets)) {
                    used[i] = true;
                    path.add(tickets.get(i).get(1));
                    backtrack(tickets);
                    path.remove(path.size() - 1);
                    used[i] = false;
                }
            }
        }
    }

    private void restore() {
        boolean flag = false;
        if (result.size() != 0) {
            for (int i = 0; i < path.size(); i++) {
                int val = path.get(i).compareTo(result.get(i));
                if (val < 0) {
                    flag = true;
                    break;
                } else if (val > 0) {
                    break;
                }
            }
        }
        if (result.size() == 0 || flag)
            result = new ArrayList<>(path);
    }

    private boolean constrain(int i, List<List<String>> tickets) {
        return result.size() == 0 || tickets.get(i).get(0).compareTo(result.get(path.size())) < 0;
    }

    private boolean bound(int i, List<List<String>> tickets) {
        return !used[i] && path.get(path.size() - 1).equals(tickets.get(i).get(0));
    }
}
